Classification of 2D shapes regardless of their position, size and orientation is an important problem in computer vision and pattern recognition. Its application is spread out into many fields, such as classification of blood cell, cancer and chromosomes, industrial inspection, target recognition, medical image recognition, scene analysis, and modeling of biological systems. Generally, shape classification is a process of comparing and recognizing shape by analyzing the information of the shape's boundaries. This seems an easy task for a human being, but is quite difficult for computers, particularly after objects are scaled, rotated and/or translated. Thus, the study of shape for the purpose of general object classification, recognition, or retrieval is an active field of current research.
Recent literature has addressed this topic, and various image processing methods have been applied. These methods can be basically classified into two techniques.
The first technique requires the projection of shape instances into a common space and then the implementation of classification on the projection space. For example: Fourier descriptors (E. Persoon, et al. “shape discrimination using Fourier descriptors” IEEE Trans. Syst. Man. Cybern, vol. 7, p 170-179, 1977), invariant moments (F. Zakaria, et. al “Fast algorithm for computation of moment invariants” Pattern Recognition, vol. 20, p 639-643, 1987), autoregressive models (S. R. Dubois, et. al “An autoregressive model approach to two-dimensional shape classification”, IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 8 p 55-66, 1986), and principal component analysis (U.S. Patent No. 2002/0164060 A1 entitled METHOD FOR CHARACTERISING SHAPES IN MEDICAL IMAGES).
An advantage of these projection-based methods is that they are independent of translation and rotation. However, a disadvantage is that they exhibit an inherent loss of information since the projection transformation is not a one-to-one correspondence. That is, one point in the projection space may correspond to several shapes whose visual appearance can be quite different. Therefore, shape classification based on such technique may lead to incorrect results.
The second technique comprises locating a set of landmark points along shape boundaries, specifying a distance measure between corresponding landmarks, and performing a distance-based clustering. As such, shape classification is reduced to the general clustering problem for which numerous solutions have been proposed. For example: M. Duta et. al. present a method using Mean Alignment Error (MAE) as a distance to measure the difference of shapes and classify shapes based on MAE. (M. Duta, et. al. “Automatic Construction of 2D Shape Models”, IEEE Trans. on Pattern Analysis and Machine Intelligence, vol 23, no. 5, p 433-446, 2001). U.S. Pat. No. 6,611,630 entitled METHOD AND APPARATUS FOR AUTOMATIC SHAPE CHARACTERIZATION and U.S. Pat. No. 6,009,212 entitled METHOD AND APPARATUS FOR IMAGE REGISTRATION are directed to a method to classify shapes based on a best match probability with an average shape of a characterizing population group. The limitation of this technique is that pair wise correspondence between the landmarks of shapes is difficult to achieve in practice because of the noise and variation among individuals.
Given the drawbacks and limitation of the prior art, there exists a need for a method to find a simple, efficient and highly accurate method for shape classification.